package array.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 39. 组合总和
 */
public class combinationSum {
    public static void main(String[] args) {
        int[] t = {2, 3, 6, 7};
        combinationSum combination = new combinationSum();
        System.out.println(combination.myCode(t, 7));
    }

    public List<List<Integer>> myCode(int[] candidates, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        backtrack1(candidates, 0, lists, new ArrayList<>(), target);
        return lists;
    }

    public void backtrack(int i, int[] nums, List<List<Integer>> lists, List<Integer> tmp, int target) {
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            if (tmp.stream().mapToInt(Integer::intValue).sum() == target) {
                lists.add(new LinkedList<>(tmp));
            }
            backtrack(j + 1, nums, lists, tmp, target);
            tmp.remove(tmp.size() - 1);
        }
    }

    public void backtrack1(int[] nums, int index, List<List<Integer>> lists, List<Integer> tmp, int target) {

        if (index == nums.length) {
            return;
        }
        if (target == 0) {
            lists.add(new ArrayList<>(tmp));
            return;
        }

        backtrack1(nums, index + 1, lists, tmp, target);
        if (target - nums[index] >= 0) {
            tmp.add(nums[index]);
            backtrack1(nums, index, lists, tmp, target - nums[index]);
            tmp.remove(tmp.size() - 1);
        }
    }
}
